#pragma once
#include<iostream>
namespace bit
{
	
	template<class k,class v>
	struct AVLTreeNode
	{
		typedef AVLTreeNode<k, v> Node;
		AVLTreeNode(const std::pair<k,v> value):
			_date(value),
			_left(nullptr),
			_right(nullptr),
			_parent(nullptr),
			_bf(0)
		{}

		AVLTreeNode(const k key,const v value):
			AVLTreeNode(std::make_pair(key,value))
		{}

		AVLTreeNode():
			AVLTreeNode(std::make_pair(k(),v()))
		{}
		
		std::pair<k, v> _date;
		Node* _left;
		Node* _right;
		Node* _parent;
		int _bf;
	};
	template<class k,class v>
	class AVLTree
	{
		typedef AVLTreeNode<k, v> Node;
	public:
		AVLTree()
		{
			_root = nullptr;
		}

		bool Insert(const std::pair<k,v>& date )
 		{
			Node* current = _root;
			Node* parent = _root;
			if (_root == nullptr)
			{
				_root = new Node(date);
				return true;
			}
			while (current)
			{
				if (date.first > current->_date.first)
				{
					parent = current;
					current = current->_right;
					continue;
				}
				else
				{
					parent = current;
					current = current->_left;
					continue;
				}
				return false;
			}
			if (date.first > parent->_date.first)
			{
				parent->_right = new Node(date);
				parent->_right->_parent = parent;
				parent->_bf++;
			}
			else
			{
				parent->_left = new Node(date);
				parent->_left->_parent = parent;
				parent->_bf--;
			}
			while (parent->_bf&&parent->_parent)
			{
				if (parent->_date.first > parent->_parent->_date.first)
				{
					parent->_parent->_bf++;
				}
				else
				{
					parent->_parent->_bf--;
				}
				current = parent;
				parent = parent->_parent;
 				if (parent->_bf > 1 || parent->_bf < -1)
				{
					if (parent->_bf == 2&&current->_bf==1)
					{
						 
						roateR(parent);
						return true;
					}
					else if(parent->_bf==-2&&current->_bf==-1)
					{
						roateR(parent, false);
						return true;
					}
					else if (parent->_bf == 2 && current->_bf == -1)
					{
						return roateRL(parent, current);
					}
					else if (parent->_bf == -2 && current->_bf == 1)
					{
						return roateRL(parent, current, false);
					}

					

				}
			}
			return true;

		}

		void roateR(Node* parent,bool isright=true)
		{
			Node* current = (isright == true ?parent->_right:parent->_left);
			Node* pnode = parent->_parent;
			if (pnode != nullptr)
			{
				if (parent == pnode->_left)
				{
					pnode->_left = current;
				}
				else
				{
					pnode->_right = current;
				}
			}
			current->_parent = pnode;
			(isright == true ?  parent->_right = current->_left:parent->_left = current->_right);
			if ((isright==true?parent->_right:parent->_left))
			{
				(isright == true? parent->_right->_parent = parent: parent->_left->_parent = parent);
			}
			(isright == true ?  current->_left = parent: current->_right = parent);
			parent->_parent = current;
			current->_bf = 0;
			parent->_bf = 0;
			if (pnode == nullptr)
				_root = current;
		}


		bool roateRL(Node*parent,Node*current, bool isright=true)
		{

			Node* currentchild = (isright == true ? current->_left:current->_right);
			int childbf = currentchild->_bf;
			roateR(current, !isright);
			roateR(parent, isright);
			if (childbf == -1)
			{
				current->_bf = 0;
				parent->_bf = 0;
				isright == true ? current->_bf = 1 : parent->_bf = 1;
				current->_bf = 1;
				currentchild->_bf = 0;
			}
			else if (childbf == 1)
			{
				current->_bf = 0;
				parent->_bf = 0;
				(isright==true?parent->_bf = -1:current->_bf=-1);
				currentchild->_bf = 0;
			}
			else if (childbf == 0)
			{
				return false;
			}
			return true;

		}
		
		void inorder()
		{
			in_inorder(_root);
			std::cout << std::endl;
		}

		
	public:
		Node* _root;
	private:
		void in_inorder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			in_inorder(root->_left);
			std::cout << root->_date.first << "__" << root->_date.second << "  ";
			in_inorder(root->_right);

		}
	};


}
